// 有n件物品，每件物品有无限多个，一个最多能背W的背包，第i件物品的重量为`weight[i]`,价值为`value[i]`，求将哪些物品放入背包，得到的价值总和最大
// 思路，01背包和完全背包的唯一不同就在于 遍历顺序
// 完全背包的物品可以多次添加，所以需要从小到大正序遍历
// 对于完全背包，一维dp，两个for循环嵌套顺序是无所谓的，只要保证下标j之前的`dp[j]`都是经过计算的就可以


function fun(inputArr) {
    let [M, N] = inputArr[0]
    let weight = inputArr[1]
    let value = inputArr[2]
    let dp = new Array(N + 1).fill(0)
    for (let i = 0; i < M; i++) {
        for (let j = weight[i]; j <= N; j++) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])            
        }        
    }
    return dp[N]
}


// 思路2，二维dp
function fun2(inputArr) {
    let [M, N] = inputArr[0]
    let weight = inputArr[1]
    let value = inputArr[2]
    let dp = new Array(M).fill(0).map(_ => new Array(N + 1).fill(0))
    // for (let j = weight[0]; j <= N; j++) {
    //     dp[0][j] = value[0]        
    // }
    for (let i = 1; i < M; i++) {
        for (let j = 0; j <= N; j++) {
            if (j < weight[i - 1]) {
                dp[i][j] = dp[i - 1][j]
            } else {
                // 可以重复放，所以这里是dp[i]
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1])
            }            
        }        
    }
    return dp[M - 1][N]
}

let inputArr = [
    [3, 4],
    [1,3,4],
    [15, 20, 30]
]

console.log(fun(inputArr))
console.log(fun2(inputArr))

